package seqlist.LeetCode;
//234. 回文链表
//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

/**
 * 思路一： 开辟一个新链表，链表的内容就是元链表的反转。
 *  然后两个链表依次比较到 null 如果全部都相等，就说明是回味链表。
 */
/*
public class Num234_isPalindrome {

    public boolean isPalindrome(ListNode head) {

        ListNode p1 = reverseList(head);
        ListNode p2 = head;

        while(p1 != null || p2 != null){

            if(p1.val != p2.val){
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }

    //头插法
    public ListNode reverseList(ListNode head) {
        ListNode dummyHead = new ListNode();

        while(head != null){
            ListNode node = new ListNode(head.val);//每次的新节点
            node.next = dummyHead.next;
            dummyHead.next = node;

            head = head.next;
        }

        return dummyHead.next;
    }

}

 */

/**
 * 思路二：反转链表的中间部分。可以先用之前的快慢指针找到链表
 * 的中间节点位置，然后在这个节点往后的链表进行反转，然后依次比较
 */

public class Num234_isPalindrome {

    public boolean isPalindrome(ListNode head) {
        //先找到中间节点的地址
        ListNode prve = middleNode(head);
        //反转链表中间位置及以后的链表
        ListNode node = reverseList(prve);

        //这里的条件也可以设置成 node ！= null
        //比如是 1~5，虽然说它中间节点反转的节点多一个，
        //但 头链表的2后面还是连接在那个中间节点 3 上面的
        while(head != prve){

            if(head.val != node.val){
                return false;
            }

            head = head.next;
            node = node.next;
        }
        return true;
    }
    //翻转链表
    public ListNode reverseList(ListNode head) {

        //当链表为空或者 只有一个是时候，就不需要翻转链表了
        if(head == null || head.next == null){
            return head;
        }
        //此时链表至少有两个节点
        ListNode dummyHead = new ListNode();//虚拟前驱
        ListNode prve = head;//因为要让第一个节点指向null
        dummyHead.next = prve;//连接一下
        while(prve.next != null){
            ListNode node  = prve.next;
            prve.next = node.next;//跳过头插节点
            node.next = dummyHead.next;//进行头插
            dummyHead.next = node;//更新新的头节点地址
        }
        return dummyHead.next;
    }

    //返回链表的中间节点地址，用的是快慢指针的方法
    public ListNode middleNode(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        //只有还有下一个节点存在，指针就可以走两步不报错，
        //一步走到最后节点上，二步走到 null 不影响。
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}